#include <iostream>
#include <cstring>
using namespace std;
using ll=long long;
const int N=110;

ll f[N][N];
ll g[N][N];
ll u[N][N];
int n,q;
ll floyd()
{
	ll ret=0;
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			ret+=f[i][j];
	return ret;
}
bool check(int x)
{
	memcpy(f,u,sizeof(f));
	int h=x/n;
	int s=x%n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i==j)
				continue;
			if(i<=s)
				f[i][j]=max(g[i][j],f[i][j]-h-1);
			else
				f[i][j]=max(g[i][j],f[i][j]-h);
			f[j][i]=f[i][j];
		}
	}
	return floyd()<=q;
}
int main()
{
	
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>u[i][j];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>g[i][j];
			f[i][j]=g[i][j];
		}
	}
	if(floyd()>q)
	{
		cout<<-1<<endl;
		return 0;
	}
	int left=0,right=10001000;
	while(left<right)
	{
		int mid=left+right>>1;
		if(check(mid))
		{
			right=mid;
		}
		else{
			left=mid+1;
		}
	}
	cout<<left<<endl;
	return 0;
}
